package com.beney.ds.sorting.abs;

// 最大值堆
public abstract class AbstractHeap extends AbstractSort {
  protected static void toHeap(Comparable[] a, int last) {
    for (int i = (last - 1) >> 1; i >= 0; --i) {
      shiftDown(a, i, last);
    }
  }

  /**
   * remove the top of the heap
   *
   * @param last last index of the heap
   */
  protected static void pop(Comparable[] heap, int last) {
    if (last < 0) return;
    swap(heap, 0, last);
    shiftDown(heap, 0, last - 1);
  }

  private static void shiftDown(Comparable[] heap, int cur, int last) {
    if (cur > (last - 1) >> 1)
      return;
    int left = cur << 1, right = left + 1;
    if (right <= last && isLess(heap, left, right)) { // 始终让left指向孩子中最大的一者
      left = right;
    }
    if (isLess(heap, cur, left)) {
      swap(heap, cur, left);
      shiftDown(heap, left, last);
    }
  }
}
